翻訳と辞書
Words near each other
・ Optionally piloted vehicle
・ Options (novel)
・ Options arbitrage
・ Options backdating
・ Options broker
・ Options Clearing Corporation
・ Options counseling
・ Options for Change
・ Optimal maintenance
・ Optimal matching
・ Optimal mechanism
・ Optimal projection equations
・ Optimal rotation age
・ Optimal solutions for Rubik's Cube
・ Optimal stopping
Optimal substructure
・ Optimal tax
・ Optimal virulence
・ Optimal, Inc.
・ Optimality criterion
・ Optimality model
・ Optimality theory
・ OptimalJ
・ Optimalniy Variant
・ Optimates
・ Optimatoi
・ Optimax
・ Optime (disambiguation)
・ OptimFROG
・ Optimisation of cutting cycles in conventional underground coal sections to improve productivity


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

Optimal substructure : ウィキペディア英語版
Optimal substructure

In computer science, a problem is said to have optimal substructure if an optimal solution can be constructed efficiently from optimal solutions of its subproblems. This property is used to determine the usefulness of dynamic programming and greedy algorithms for a problem.
Typically, a greedy algorithm is used to solve a problem with optimal substructure if it can be proved by induction that this is optimal at each step.〔 Otherwise, provided the problem exhibits overlapping subproblems as well, dynamic programming is used. If there are no appropriate greedy algorithms and the problem fails to exhibit overlapping subproblems, often a lengthy but straightforward search of the solution space is the best alternative.

In the application of dynamic programming to mathematical optimization, Richard Bellman's Principle of Optimality is based on the idea that in order to solve a dynamic optimization problem from some starting period ''t'' to some ending period ''T'', one implicitly has to solve subproblems starting from later dates ''s'', where ''tBellman equation, which shows how the value of the problem starting from ''t'' is related to the value of the problem starting from ''s''.
==Example==
Consider finding a shortest path for travelling between two cities by car, as illustrated in Figure 1. Such an example is likely to exhibit optimal substructure. That is, if the shortest route from Seattle to Los Angeles passes through Portland and then Sacramento, then the shortest route from Portland to Los Angeles must pass through Sacramento too. That is, the problem of how to get from Portland to Los Angeles is nested inside the problem of how to get from Seattle to Los Angeles. (The wavy lines in the graph represent solutions to the subproblems.)
As an example of a problem that is unlikely to exhibit optimal substructure, consider the problem of finding the cheapest airline ticket from Buenos Aires to Kyiv. Even if that ticket involves stops in Miami and then London, we can't conclude that the cheapest ticket from Miami to Kyiv stops in London, because the price at which an airline sells a multi-flight trip is usually not the sum of the prices at which it would sell the individual flights in the trip.

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「Optimal substructure」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.